import collections
from typing import List

from sortedcontainers import SortedDict


class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        # 间隔插入
        n = len(barcodes)
        num_freq = collections.Counter(barcodes)
        a = list(num_freq.items())
        # ----------- 按照freq降序排列
        a.sort(key=lambda x: -x[1])
        # ----------- 间隔插入
        res = [0 for _ in range(n)]
        i = 0
        for x, fx in a:
            for _ in range(fx):
                if i >= n:
                    i = 1
                res[i] = x
                i += 2
        return res


if __name__ == '__main__':
    sol = Solution()
    # print(sol.rearrangeBarcodes([1, 1, 1, 2, 3, 2]))
    print(sol.rearrangeBarcodes([1, 1, 1, 2, 3, 2, 4, 6, 5, 7]))
